package ch4.part5;

import java.util.Arrays;

/**
 * 优化后的计数排序，稳定排序
 *
 * @author liuwanxiang
 * @version 2019/06/15
 */
public class OptimizeCountSort {


    private static int[] sort(int[] array) {

        // 确定数组的最大值和最小值，确定计数器数组的长度和偏移量
        int min = 0, max = 0;
        for (int value : array) {
            if (max < value) {
                max = value;
            }
            if (min > value) {
                min = value;
            }
        }
        int len = max - min + 1;

        // 构建计数器数组，元素每出现一次，该位置计数器++
        int[] countArray = new int[len];
        for (int value : array) {
            countArray[value - min]++;
        }

        // Count数组，后一个元素均等于自己值+前一元素值
        // 也可以理解为Count数组中存放的就是元素的位置下标+1
        for (int i = 1; i < len; i++) {
            countArray[i] += countArray[i - 1];
        }

        // 倒序循环原数组，以构建有序数组
        int[] sortedArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            sortedArray[countArray[array[i] - min] - 1] = array[i];
            countArray[array[i] - min]--;
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] array = {11, 10, 12, 19, 13, 16, 19, 14, 18, 17, 16, 15};
        int[] sortedArray = sort(array);
        System.out.println(Arrays.toString(sortedArray));
    }

}
